package oj0522;

import java.util.Arrays;
import java.util.Scanner;

class HuffmanNode {
    int weight; //结点的权值
    int parent; //父结点下标
    int lchild; //左孩子下标
    int rchild; //右孩子下标

    HuffmanNode(int weight) {
        this.weight = weight;
        this.parent = -1;
        this.lchild = -1;
        this.rchild = -1;
    }

    void display() { //结点信息输出
        System.out.println(weight + "\t"
                + parent + "\t"
                + lchild + "\t"
                + rchild);
    }
}

class HuffmanTree {
    private int nodeNum;//权重结点个数
    private HuffmanNode[] huffTree;//定义哈夫曼树顺序表

    public HuffmanTree(int[] data) {
        this.nodeNum = data.length;
        this.huffTree = new HuffmanNode[2*this.nodeNum - 1];
        //初始化，把权重放入哈夫曼树顺序表
        for (int i = 0; i < this.huffTree.length; i++) {
            if (i < this.nodeNum) {
                huffTree[i] = new HuffmanNode(data[i]);
            } else {
                huffTree[i] = new HuffmanNode(0);
            }
        }
    }

    private int[] select2Min() {
        //实现如何选到当前还没被使用的最小值和次小值的下标
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        int index1 = -1;
        int index2 = -1;

        for (int i = 0; i < 2*nodeNum-1; i++) {
            HuffmanNode node = huffTree[i];

            if (node.parent != -1){
                continue;
            }
            if (node.weight == 0) break;
            if (node.weight < min1) {
                min2 = min1;
                index2 = index1;
                min1 = node.weight;
                index1 = i;
            } else if (node.weight < min2) {
                min2 = node.weight;
                index2 = i;
            }
        }
        return new int[]{index1, index2};
    }

    public void create() {
        //初始化哈夫曼树的节点
        //为结点附上相应的权值
        //进行哈夫曼树的建立
        for (int i = nodeNum; i<2*nodeNum - 1 ; i++){
            int[] minIndexs = select2Min();
            int min1 = minIndexs[0];
            int min2 = minIndexs[1];

            huffTree[i].weight = huffTree[min1].weight + huffTree[min2].weight;
            huffTree[i].lchild = min1;
            huffTree[i].rchild = min2;
            huffTree[min1].parent = i;
            huffTree[min2].parent = i;

        }
    }

    public void display() {
        for (int i = 0; i < huffTree.length; i++) {
            System.out.print(i + "\t");
            huffTree[i].display();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[] data = new int[num];
        for (int i = 0; i < num; i++) {
            data[i] = scanner.nextInt();
        }
        HuffmanTree t = new HuffmanTree(data);
        t.create();
        t.display();
        scanner.close();
    }
}